// linked_hash_map.h
// list 实现版本
#ifndef LINKED_HASH_MAP_H
#define LINKED_HASH_MAP_H

#ifdef _WIN32
    #pragma warning(disable: 4786)
    #pragma warning(disable: 4503)
#endif

#include <map>
#include <list>
#include <utility> // for std::pair

// 跨平台互斥锁封装
#ifdef _WIN32
    #include <windows.h>

    typedef CRITICAL_SECTION mutex_type;
    inline void mutex_init(mutex_type* m) { InitializeCriticalSection(m); }
    inline void mutex_destroy(mutex_type* m) { DeleteCriticalSection(m); }
    inline void mutex_lock(mutex_type* m) { EnterCriticalSection(m); }
    inline void mutex_unlock(mutex_type* m) { LeaveCriticalSection(m); }
#else
    #include <pthread.h>
    typedef pthread_mutex_t mutex_type;
    inline void mutex_init(mutex_type* m) { pthread_mutex_init(m, NULL); }
    inline void mutex_destroy(mutex_type* m) { pthread_mutex_destroy(m); }
    inline void mutex_lock(mutex_type* m) { pthread_mutex_lock(m); }
    inline void mutex_unlock(mutex_type* m) { pthread_mutex_unlock(m); }
#endif

template <typename K, typename V>

class LinkedHashMap {
public:
    typedef K key_type;
    typedef V mapped_type;
    typedef std::pair<const K, V> value_type;
    typedef typename std::list<value_type>::const_iterator const_iterator;
    typedef typename std::list<value_type>::iterator list_iterator;
    typedef std::map<K, list_iterator> map_type;
    typedef typename map_type::iterator map_iterator;
    typedef typename map_type::const_iterator map_const_iterator;

    LinkedHashMap() {
        mutex_init(&mtx_);
    }

    ~LinkedHashMap() {
        mutex_destroy(&mtx_);
    }

    // 插入或更新
    // 插入或赋值
    void insert(const K& key, const V& value) {
        mutex_lock(&mtx_);
        map_iterator map_it = map_.find(key);
        if (map_it != map_.end()) {
            // 更新
            map_it->second->second = value;
        } else {
            // 插入到 list 尾部
            list_.push_back(value_type(key, value));
            list_iterator lit = list_.end();
            --lit;
            map_[key] = lit;
        }
        mutex_unlock(&mtx_);
    }

    // 查找（只读），成功返回 true 并输出值
    bool get(const K& key, V& out) const {
        mutex_lock(&mtx_);
        map_const_iterator map_it = map_.find(key);
        if (map_it != map_.end()) {
            out = map_it->second->second;
            mutex_unlock(&mtx_);
            return true;
        }
        mutex_unlock(&mtx_);
        return false;
    }

    // 删除
    bool erase(const K& key) {
        mutex_lock(&mtx_);
        map_iterator map_it = map_.find(key);
        if (map_it == map_.end()) {
            mutex_unlock(&mtx_);
            return false;
        }

        // 从 list 中删除
        list_.erase(map_it->second);
        // 从 map 中删除
        map_.erase(map_it);
        mutex_unlock(&mtx_);
        return true;
    }

    // 清空
    void clear() {
        mutex_lock(&mtx_);
        map_.clear();
        list_.clear();
        mutex_unlock(&mtx_);
    }

    // 获取大小
    size_t size() const {
        mutex_lock(&mtx_);
        size_t s = map_.size();
        mutex_unlock(&mtx_);
        return s;
    }

    bool empty() const {
        mutex_lock(&mtx_);
        bool e = map_.empty();
        mutex_unlock(&mtx_);
        return e;
    }

    // 顺序遍历迭代器（注意：返回后容器可能被修改！）
    const_iterator begin() const {
        mutex_lock(&mtx_);
        const_iterator it = list_.begin();
        mutex_unlock(&mtx_);
        return it;
    }

    const_iterator end() const {
        mutex_lock(&mtx_);
        const_iterator it = list_.end();
        mutex_unlock(&mtx_);
        return it;
    }

private:
    mutable mutex_type mtx_;
    map_type map_;
    std::list<value_type> list_;

    // 禁止拷贝
    LinkedHashMap(const LinkedHashMap&);
    LinkedHashMap& operator=(const LinkedHashMap&);
};

#endif // LINKED_HASH_MAP_H